package com.singzi.leetcode.jianzhiOffer2;

import java.util.Random;
import java.util.TreeMap;
import java.util.TreeSet;

public class T0071 {
    public static void main(String[] args) {

    }
}
class Solution0071 {

    int []w;
    Random random;
    int sum = 0;
    TreeMap<Integer, Integer> map;
    public Solution0071(int[] w) {
        this.w = w;
        random = new Random();
        map = new TreeMap<>();
        for(int i = 0;i < w.length;i++){
            sum += w[i];
            map.put(sum,i);
        }
    }

    public int pickIndex() {

        int randomInt = random.nextInt(sum);
        int index = map.get(map.ceilingKey(randomInt));
        return index;

    }
}